package com.hsh.utils.datastructure;

import lombok.AllArgsConstructor;
import lombok.Data;

import javax.sound.midi.Soundbank;
import javax.xml.soap.Node;
import java.util.Stack;

/**
 * Created by root on 17-4-25.
 */
public class BinTree {
    int size;
    private BinNode root;

    public void insertAsRoot(BinNode root) {
        size = 1;
        this.root = root;
    }

    public void insertAsLc(BinNode node, BinNode lChild) {
        node.setLChild(lChild);
        this.size++;
    }

    public void insertAsRc(BinNode node, BinNode rChild) {
        node.setRChild(rChild);
        this.size++;
    }

    public void preOrderByIterator (BinNode node) {
        if (node == null) {
            return;
        }
        visit(node);
        travalPre(node.getLChild());
        travalPre(node.getRChild());
    }

    public void preOrderByTraversal (BinNode node) {
        Stack<BinNode> rNodeStack = new Stack();
        while (true) {
            while ( node != null) {
                System.out.print(node.getValue() + ";");
                if (node.getRChild() != null ){
                    rNodeStack.push(node.getRChild());
                }
                BinNode lChild = node.getLChild();
                node = lChild;
            }

            if (rNodeStack.isEmpty()) {
                break;
            }
            node = rNodeStack.pop();
        }
    }

    public void inOrderByIterator (BinNode node) {
        if (node == null) {
            return;
        }

        travalIn(node.getLChild());
        visit(node);
        travalIn(node.getRChild());
    }


    public void inOrderByTraversal (BinNode node) {
        Stack<BinNode> nodeStack = new Stack<>();

        while (true) {
            //go alone left branch
            while(node != null) {
                nodeStack.push(node);
                node = node.getLChild();
            }
            if (nodeStack.isEmpty()) return;
            node = nodeStack.pop();
            System.out.print(node.getValue()+";");
            node = node.getRChild();
        }

    }



    public void postOrderByIterator (BinNode node) {
        if (node == null) {
            return;
        }

        travalPost(node.getLChild());
        travalPost(node.getRChild());
        visit(node);
    }

    private void travalPre(BinNode node) {
        preOrderByIterator(node);
    }

    private void travalIn(BinNode node) {
        inOrderByIterator(node);
    }

    private void travalPost(BinNode node) {
        postOrderByIterator(node);
    }

    private void visit(BinNode node) {
        System.out.print(node.getValue() + ";");
    }



    @Data
    @AllArgsConstructor
    private static class BinNode<T> {
        private T value;
        private BinNode parent, lChild, rChild;
        private int height;
        private int npl; //null path length,左式堆,也可用height代替
    }

    /**
     *
     *          root
     *      /              \
     *     node1            node2
     *   /     \           /      \
     * node3    node4     node5   node6
     * @param args
     */
    public static void main(String[] args) {
        BinTree binTree = new BinTree();
        BinNode<Integer> root = new BinNode<Integer>(11, null, null, null, 0, 0);
        BinNode<Integer> node1 = new BinNode<Integer>(1, null, null, null, 0, 0);
        BinNode<Integer> node2 = new BinNode<Integer>(2, null, null, null, 0, 0);
        BinNode<Integer> node3 = new BinNode<Integer>(3, null, null, null, 0, 0);
        BinNode<Integer> node4 = new BinNode<Integer>(4, null, null, null, 0, 0);
        BinNode<Integer> node5 = new BinNode<Integer>(5, null, null, null, 0, 0);
        BinNode<Integer> node6 = new BinNode<Integer>(6, null, null, null, 0, 0);

        binTree.insertAsRoot(root);
        binTree.insertAsLc(root, node1);
        binTree.insertAsRc(root, node2);
        binTree.insertAsLc(node1, node3);
        binTree.insertAsRc(node1, node4);
        binTree.insertAsLc(node2, node5);
        binTree.insertAsRc(node2, node6);

        binTree.preOrderByIterator(root);
        System.out.println("");
        binTree.preOrderByTraversal(root);
        System.out.println("");
        binTree.inOrderByIterator(root);
        System.out.println("");
        binTree.inOrderByTraversal(root);
        System.out.println("");
        binTree.postOrderByIterator(root);

    }
}
